package search;

import java.util.Arrays;

/**
 * 记一次顺序表查找
 *
 * @author miweidong
 * @date 2021-09-03 10:14
 */
public class SequenceSearch {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 0, 7, 8, 9};
        int i = seqSearch1(arr, 10);
//        int i = binarySearch(arr, 0);
        System.out.println(i);
    }

    public static int seqSearch(int[] arr, int key) {
        int i = 0;
        int length = arr.length;
        while (i < length && arr[i] != key) {
            i++;
        }
        if (i >= length) {
            throw new RuntimeException("未找到匹配值");
        }
        return i + 1;
    }

    public static int seqSearch1(int[] arr, int key) {
        int i = 0;
        int last = arr.length;
        int[] copy = Arrays.copyOf(arr, arr.length + 1);
        copy[last] = key;
        while (copy[i] != key) {
            i++;
        }
        if (i == arr.length) {
            throw new RuntimeException("未找到匹配值");
        }
        return i + 1;
    }

    /**
     * 确保数组有序
     */
    public static int binarySearch(int[] arr, int key) {
        int i = 0;
        int low = 0;
        int high = arr.length - 1;
        int middle;
        while (i < arr.length && low <= high) {
            middle = (low + high) / 2;
            if (arr[middle] == key) {
                return middle + 1;
            }
            if (arr[middle] > key) {
                high = middle - 1;
            } else {
                low = middle + 1;
            }
        }
        throw new RuntimeException("未找到匹配值");
    }

    /**
     * 分块查找
     * 将数组分成多段，每个块内的元素个数可不一致，根据情况而定
     * 且，块间大小有序递增，块内可无序
     * 找到每个块的开始位置，作为key,将块内的最大元素作为value（索引表），索引表有序递增
     * 当查找一个元素时，先查索引表（可以使用二分查找/顺序查找），确定元素所在块的位置，
     * 其次，块内顺序查找元素，因为块内元素无序
     * 块大小如何确定呢？
     * 书上说: 根号下元素个数
     * ext: 将索引表改成链式，每个节点的数据域存放对应块内元素集  （动态查找表）
     */
    public static int blockSearch(Index[] index, int[] arr, int key) {
        // 索引表比对关键字，定位对应块

        // 块内顺序查找

        return 0;
    }

    static class Index {
        /**
         * 开始位置
         */
        private int start;

        /**
         * 最大值
         */
        private int maxKey;

        /**
         * 块长度
         */
        private int length;

    }

}
